/*
MIT License

Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,

https://bmstu.codes/lsx/simodo
*/

#include "simodo/parser/automaton/PushdownAutomaton.h"
#include "simodo/inout/convert/functions.h"
#include "simodo/inout/token/InputStream.h"
#include "simodo/inout/format/fmt.h"

#include <algorithm>
#include <vector>
#include <cassert>

namespace simodo::parser
{
    namespace 
    {
        static uint16_t MAX_ERROR_COUNT = 5;
        static size_t   MAX_ERROR_RECOVER_ATTEMPTS = 5;

        AstBuilder_null null_builder;
    }

    inline inout::Token error_token(const std::u16string & lexeme, const inout::TokenLocation & location)
    {
        return { {lexeme, inout::LexemeType::Error}, lexeme, location };
    }


    PushdownAutomaton::PushdownAutomaton(inout::Reporter_abstract &m, Grammar &g, 
                                         const inout::uri_set_t & files)
        : _m(m)
        , _g(g)
        , _files(files)
        , _uri_index(files.size()-1)
        , _builder(null_builder)
    {
        assert(!files.empty());
    }

    PushdownAutomaton::PushdownAutomaton(inout::Reporter_abstract &m, Grammar &g,
                                         const inout::uri_set_t & files,
                                         AstBuilder_interface & builder)
        : _m(m)
        , _g(g)
        , _files(files)
        , _uri_index(files.size()-1)
        , _builder(builder)
    {
        assert(!files.empty());
    }

    bool PushdownAutomaton::parse() 
    {
        /// \todo Несовместима с Windows
        std::ifstream in(_files[_uri_index]);

        if (!in)
        {
            _m.reportFatal(inout::fmt("Ошибка при открытии файла '%1'")
                            .arg(_files[_uri_index]));
            return false;
        }

        inout::InputStream stream(in);

        return parse(stream);
    }

    /// \todo Изменить имя интерфейса SemanticTreeBuilder_interface
    bool PushdownAutomaton::parse(inout::InputStream_interface & stream)
    {
        assert(!_g.parse_table.empty());
        assert(_g.first_compound_index < _g.columns.size());

        // inout::LexicalParameters param = makeLexicalParameters(_g);

        inout::Tokenizer tokenizer(_uri_index, stream, _g.lexical);

        inout::Token token = getToken(tokenizer,_builder);
        inout::Token delayed_token = error_token(token.lexeme(), token.location());

        while(token.type() == inout::LexemeType::NewLine)
            token = getToken(tokenizer,_builder);

        // input is empty
        if (token.type() == inout::LexemeType::Empty)
            return true;

        size_t   column_no   = _g.getTerminalColumnIndex(token);
        bool     success     = true;
        bool     end         = false;
        uint16_t error_count = 0;

        std::vector<PushdownAutomatonState> states;
        states.emplace_back(0, 
                            _g.first_compound_index, 
                            inout::Token { _g.columns[_g.first_compound_index], token.location()});

        // Вызов генератора
        if (!_builder.onStart(_g.handlers))
            success = false;

        // Цикл разбора
        while(!end && error_count < MAX_ERROR_COUNT)
        {
            size_t state_no = states.back().getStateNo();

            if (!_g.findFsmValue(state_no,column_no))
            {
                reportSyntaxError(states, token);
                error_count ++;
                success = false;

                // Пытаемся восстановиться после ошибки методом "паники"
                /// \todo Нужно будет доработать алгоритм восстановления после ошибок на что-то более интеллектуальное
                size_t i = 0;
                for(; i < MAX_ERROR_RECOVER_ATTEMPTS; ++i) // Ограничиваем кол-во попыток
                {
                    if (delayed_token.type() != inout::LexemeType::Error) {
                        token = delayed_token;
                        delayed_token = error_token(token.lexeme(), token.location());
                    }
                    else {
                        token = getToken(tokenizer,_builder);
                        while(token.type() == inout::LexemeType::NewLine)
                            token = getToken(tokenizer,_builder);
                    }
                    column_no = _g.getTerminalColumnIndex(token);
                    if (_g.findFsmValue(state_no,column_no) || token.type() == inout::LexemeType::Empty)
                        break;
                }

                if (i == MAX_ERROR_RECOVER_ATTEMPTS || !_g.findFsmValue(state_no,column_no))
                    break;
            }

            Fsm_value_t   fsm_value = _g.getFsmValue(state_no,column_no);
            FsmActionType action    = _g.unpackFsmAction(fsm_value);

            switch(action)
            {
            case FsmActionType::Acceptance:
                end = true;
                break;

            case FsmActionType::Error:
                _m.reportError(token.makeLocation(_files), inout::fmt("Синтаксическая ошибка"));
                error_count ++;
                success = false;
                break;

            case FsmActionType::Reduce:
                {
                    size_t              rule_no = _g.unpackFsmLocation(fsm_value);
                    const GrammarRule & r       = _g.rules.at(rule_no);

                    assert(states.size() >= r.pattern.size());

                    // Вызов генератора
                    inout::TokenLocation prod_location(states.back().location());
                    std::vector<inout::Token> pattern;
                    pattern.reserve(r.pattern.size());

                    for(size_t i=0; i < r.pattern.size() ; ++i) {
                        inout::Token t = states.back();
                        if (i > 0) 
                            prod_location.merge(t.location());
                        pattern.insert(pattern.begin(), t);
                        /// \todo Нужно проверить: корректно ли именно тут сбрасывать состояние с точки зрения корректного восстановления
                        /// после синтаксической ошибки, значительная часть которых происходит во время редукции (см. обработку ниже).
                        states.pop_back();
                    }

                    size_t symbol_index = _g.getCompoundColumnIndex(r.production);
                    if (symbol_index == _g.columns.size()) {
                        _m.reportWithPosition(inout::SeverityLevel::Fatal, token.makeLocation(_files), 
                                              inout::fmt("Сбой при определении номера символа продукции '%1'")
                                              .arg(r.production));
                        success = false;
                        break;
                    }
                    size_t line = states.back().getStateNo();

                    if (!_g.findFsmValue(line,symbol_index)) {
                        reportSyntaxError(states, token);
                        error_count ++;
                        success = false;

                        if (token.type() == inout::LexemeType::Empty)
                            symbol_index = 0;
                        else
                            // Восстановление после ошибки путём подстановки подходящего символа
                            // (доходим до 1, т.к. 0 - это конец файла)
                            for(symbol_index=_g.first_compound_index-1; symbol_index > 0; --symbol_index)
                                if (_g.findFsmValue(line,symbol_index)) {
                                    token = { _g.columns[symbol_index], token.location() };

                                    if (isLexemeValid(states,token)) {
                                        column_no = symbol_index;
                                        break;
                                    }
                                }

                        if (symbol_index == 0) {
                            end = true;
                            break;
                        }
                    }
                    Fsm_value_t   val = _g.getFsmValue(line,symbol_index);
                    FsmActionType act = _g.unpackFsmAction(val);

                    if (act == FsmActionType::Shift) {
                        size_t st = _g.unpackFsmLocation(val);
                        states.emplace_back(st, symbol_index, inout::Token { inout::LexemeType::Compound, r.production, prod_location});
                    }
                    else {
                        _m.reportWithPosition(inout::SeverityLevel::Fatal, token.makeLocation(_files), 
                                              inout::fmt("При обработке приведения возникло недопустимое состояние"));
                        success = false;
                        break;
                    }

#ifdef AST_BUILDER_DEBUG
                    if (error_count == 0 &&
                        !_builder.onProduction(state_no, rule_no,
                                            inout::Token { {r.production, inout::LexemeType::Compound}, r.production, prod_location },
                                            pattern,
                                            r.reduce_action,
                                            line,
                                            states.back().getStateNo())) {
                        success = false;
                        end = true;
                        break;
                    }
#else
                    if (error_count == 0 &&
                        !_builder.onProduction(
                                            inout::Token { {r.production, inout::LexemeType::Compound}, r.production, prod_location },
                                            pattern,
                                            r.reduce_action)) {
                        success = false;
                        end = true;
                        break;
                    }
#endif
                }
                break;

            case FsmActionType::Shift:
                {
                    Fsm_value_t val   = _g.getFsmValue(state_no,column_no);
                    size_t      shift = _g.unpackFsmLocation(val);

#ifdef AST_BUILDER_DEBUG
                    if (!_builder.onShift(state_no, _g.columns[column_no], column_no, shift)) {
                        success = false;
                        end = true;
                        break;
                    }
#endif
                    PushdownAutomatonState  ps(shift,column_no,token);

                    // Фрагмент кода, анализирующего возможность замены символа новой строки на заданный терминал
                    // (обычно это символ ';')

                    // Логика проверки возможности замены следующая:
                    // 1. Если подменяемый символ не допустим грамматикой языка - замена не производится
                    // 2. Если следующий символ после новой строки допустим грамматикой языка - замена не производится

                    // Чтобы проверить допустимость символа-замены и следующего символа недостаточно проверить текущее
                    // состояние разбора, так как оба символа могут участвовать в текущем контексте, но во вложенных
                    // структурах (например, символ '}' может быть допустим грамматикой в выражении для лямбды и нужно
                    // раскрутить стек состояний, чтобы убедиться, что мы находимся действительно в обработке лямбды,
                    // а не в конце выражения и символ '}' не является концом блока операторов).
                    // Для проверки допустимости токена в данном контексте по глубине стека состояний используется
                    // метод isTokenValid.

                    if (delayed_token.type() != inout::LexemeType::Error) {
                        token = delayed_token;
                        delayed_token = error_token(token.lexeme(), token.location());
                    }
                    else {
                        token = getToken(tokenizer,_builder);

                        if (token.type() == inout::LexemeType::NewLine) {
                            inout::Token nl_token = token;

                            while(token.type() == inout::LexemeType::NewLine)
                                token = getToken(tokenizer,_builder);

                            // Для подмены символа замещения нужно, чтобы следующий символ не соответствовал грамматике

                            std::vector<PushdownAutomatonState> full_stack  = states;

                            full_stack.push_back(ps);

                            if (!isLexemeValid(full_stack,token)) {
                                // Не соответствует...

                                nl_token = {inout::LexemeType::Punctuation, nl_token.lexeme(), nl_token.location() };

                                // Для подмены символа замещения нужно, чтобы символ замещения соответствовал грамматике

                                if (isLexemeValid(full_stack,nl_token)) {
                                    // Соответствует...

                                    delayed_token = token;
                                    token = nl_token;
                                }
                            }
                        }
                    }

                    // Штатная обработка

                    column_no = _g.getTerminalColumnIndex(token);

                    if (column_no == _g.columns.size()) {
                        // Полученный символ (токен) не предусмотрен данной грамматикой.
                        // Такое может быть, например, если грамматика не предусматривает числовых констант, а она таки записана.
                        // Или, что чаще бывает, введены ошибочные символы, которых нет в лексике грамматики (LexemeType::Error)
                        reportSyntaxError(states, token);
                        error_count ++;
                        success = false;

                        // Простейший вариант восстановления - попытаться заменить данный токен на один из ожидаемых
                        // (начинаем с конца, т.к. в конце списка, как правило, наиболее обобщённые токены)
                        // (доходим до 1, т.к. 0 - это конец файла)
                        /// \todo Нужно будет доработать алгоритм восстановления на что-то более интеллектуальное
                        for(size_t i=_g.first_compound_index-1; i > 0; --i)
                            if (_g.findFsmValue(shift,i)) {
                                token = { _g.columns[i], token.location() };
                                column_no = i;
                                break;
                            }
                    }
                    states.push_back(ps);
                }
                break;
            }
        }

        if (error_count == MAX_ERROR_COUNT)
            _m.reportInformation(inout::fmt("Превышено допустимое количество ошибок, разбор прерван"));
        else if (!end)
            _m.reportInformation(inout::fmt("Не удалось выполнить восстановление состояния разбора после синтаксической ошибки, разбор прерван"));

        if (!_builder.onFinish(success, _g.handlers))
            success = false;

        return success;
    }

    inout::Token PushdownAutomaton::getToken(inout::Tokenizer & tz, AstBuilder_interface & builder) const
    {
        inout::Token t = tz.getAnyToken();
        
        builder.onTerminal(t);

        while(t.type() == inout::LexemeType::Comment) {
            t = tz.getAnyToken();
            builder.onTerminal(t);
        }

        return t;
    }

    void PushdownAutomaton::reportSyntaxError(const std::vector<PushdownAutomatonState> &states, const inout::Token &t) const
    {
        assert(!states.empty());

        const PushdownAutomatonState & parser_state = states.back();
        std::string                 briefly;
        std::string                 atlarge;
        std::vector<std::string>    expected;

        if (t.type() == inout::LexemeType::Empty)
            briefly += inout::fmt("Преждевременный конец файла");
        else
            briefly += inout::fmt("Неподходящий входной символ '%1'.").arg(t.lexeme());

        const FsmState_t & si = _g.states.at(parser_state.getStateNo());

        // Просматриваем позиции текущего состояния
        for(const FsmStatePosition &p : si) {
            const GrammarRule &rule = _g.rules.at(p.rule_no);

            if (atlarge.empty()) {
                if (p.position == 0)
                    atlarge = inout::fmt("При разборе правила '%1").arg(rule.production);
                else {
                    if (p.position == rule.pattern.size())
                        atlarge = inout::fmt("После разбора правила '%1").arg(rule.production);
                    else if (rule.pattern.at(p.position-1).type() == inout::LexemeType::Compound)
                        atlarge = inout::fmt("После разбора правила '%1").arg(rule.pattern.at(p.position-1).lexeme());
                    else
                        atlarge = inout::fmt("При разборе правила '%1").arg(rule.production);
                }
                atlarge += inout::fmt("' (состояние КА = %1) ").arg(inout::toU16(std::to_string(parser_state.getStateNo())));

                if (t.type() == inout::LexemeType::Empty)
                    atlarge += inout::fmt("достигнут конец файла");
                else
                    atlarge += inout::fmt("получен неподходящий символ '%1'").arg(t.lexeme());

                atlarge += inout::fmt(", вместо ожидаемых символов: ");
            }
        }

        for(size_t i=0; i < _g.first_compound_index; ++i)
            if (isLexemeValid(states,_g.columns[i]))
                expected.emplace_back(getLexemeMnemonic(_g.columns.at(i)));

        // Отображаем перечень ожидаемых символов
        for(auto st=expected.begin(); st != expected.end(); ++st) {
            if (st != expected.begin())
                atlarge += ", ";
            atlarge += *st;
        }

        atlarge += inout::fmt("\nПозиция разбора: %1").arg(inout::getLocationString(t.makeLocation(_files)));

        _m.reportError(t.makeLocation(_files), briefly, atlarge);
    }

    bool PushdownAutomaton::isLexemeValid(std::vector<PushdownAutomatonState> states, const inout::Lexeme &lexeme) const
    {
        assert(!states.empty());

        // Для определения допустимости заданного символа в текущем контексте выполняется следующий алгоритм:

        // Необходимо для каждого состояния стека состояний, начиная с верхнего, убедиться, что:
        // 1. если предусмотрен сдвиг или завершение, то символ является разрешённым, возвращаем true
        // 2. иначе: для заданного символа предусмотрена свёртка, спускаемся ниже по стеку состояний.
        // 3. достижение конца стека не должно произойти (по идее).

        size_t column_no = _g.getTerminalColumnIndex(lexeme);

        if (column_no >= _g.columns.size())
            return false;

        while(!states.empty()) {
            const PushdownAutomatonState & ps         = states.back();
            size_t                         state_no   = ps.getStateNo();

            if (!_g.findFsmValue(state_no, column_no))
                return false;

            Fsm_value_t         fsm_value  = _g.getFsmValue(state_no, column_no);
            FsmActionType       fsm_action = _g.unpackFsmAction(fsm_value);

            if (fsm_action == FsmActionType::Error)
                return false;

            if (fsm_action == FsmActionType::Shift || fsm_action == FsmActionType::Acceptance)
                return true;

            size_t              rule_no      = _g.unpackFsmLocation(fsm_value);
            const GrammarRule & rule         = _g.rules.at(rule_no);
            size_t              pattern_size = rule.pattern.size();

            for(size_t i=0; i < pattern_size; ++i)
                states.pop_back();

            size_t symbol_index = _g.getCompoundColumnIndex(rule.production);
            assert(symbol_index < _g.columns.size());

            size_t line = states.back().getStateNo();

            if(!_g.findFsmValue(line,symbol_index))
                return false;

            Fsm_value_t   val    = _g.getFsmValue(line,symbol_index);
            FsmActionType act    = _g.unpackFsmAction(val);

            assert(act == FsmActionType::Shift);

            size_t st = _g.unpackFsmLocation(val);

            states.emplace_back(st, symbol_index, inout::Token {inout::LexemeType::Compound, rule.production, ps.location()});
        }

        return false;
    }

    // inout::LexicalParameters PushdownAutomaton::makeLexicalParameters(const Grammar &g)
    // {
    //     return g.lexical;
    // }

}